Recap
strategic game $G=(N,S,u)$:
$N = \{1,\dots,n\}$ set of players
$S_i$ (pure) strategies
$u_i: S \to \IR$ utility fct. of player $i$
$s^* \in S$
(pure) Nash equilibrium (PNE) if
$u_i(s^*) \geq u_i(s_i,s^*_{-i})$ f.a. $s_i \in S_i, i \in N$.
$\iff s^* \in B(s^*) \coloneqq \prod_i B_i(s^*_{-i})$, where $B_i(s^*_{-i})$ is the set of best responses (for player $i$)
Rabin's Poison Puzzle:
(for the case: weak poison row < weak poison column < strong poison row < strong poison column)
$O$ $A$ $B$ $C$ $O$ $(-1,1)$ $(-1,1)$ $(-1,-1)$ $(-1,-1)$ $A$ $(1,-1)$ $(-1,-1)$ $(-1,1)$ $(-1,-1)$ $B$ $(-1,-1)$ $(1,-1)$ $(-1,-1)$ $(-1,1)$ $C$ $(-1,1)$ $(-1,-1)$ $(1,-1)$ $(-1,-1)$
Strategies:
$O$: bring your strongest poison
$A$: drink weak poison before, bring water
$B$: bring water
$C$: drink weak poison before, bring your strongest poison
PNE via Best-Response-Correspondence
Input: Finite strategic game $G=(N,S,u)$
Output: Set of all PNE of $G$
For each $i \in N, s_{-i} \in S_{-i}$ Do mm For each $s_i \in B_i(s_{-i})$ Do mmmm mark $(s_i,s_{-i})$ with ${*_i}$Return all strategy profiles which have all marks ${*_{i}}$
$G=(N,S,u)$ zero sum game if $N = [2]$ and $u_1 = -u_2$.
Thm. 1.16: In zero-sum games the following are equivalent:
$(k^*,\ell^*)$ PNE with value $v^* \coloneqq u_1(k^*,\ell^*)$
$k^* \in \arg\max_{k \in S_1}(\min_{\ell \in S_2} u_1(k,\ell))$, $\ell^* \in \arg\min_{\ell \in S_2}(\max_{k \in S_1} u_1(k,\ell))$ and
\[\max_{k \in S_1}(\min_{\ell \in S_2} u_1(k,\ell))=v^* =\min_{\ell \in S_2}(\max_{k \in S_1} u_1(k,\ell)).\]
Cor. 1.22: In finite zero-sum games the following are equivalent:
$(x^*,y^*)$ MNE with value $v^* \coloneqq U_1(x^*,y^*)$
$x^* \in \arg\max_{x \in \Delta(S_1)}(\min_{y \in \Delta(S_2)} U_1(x,y))$, $y^* \in \arg\min_{y \in \Delta(S_2)}(\max_{x \in \Delta(S_1)} U_1(x,y))$ and
\[\max_{x \in \Delta(S_1)}(\min_{y \in \Delta(S_2)} U_1(x,y))=v^* =\min_{y \in \Delta(S_2)}(\max_{x \in \Delta(S_1)} U_1(x,y)).\]
mixed extension $(N,\Delta,U)$ of $G$:
$\Delta(S_i) \coloneqq \set{x_i \in [0,1]^{S_i} \sMid \sum_{s_i \in S_i}x_{is_i}=1}$ mixed strategies mixed strategy profile
$U_i: \Delta \to \IR, x \mapsto \sum_{s \in S} x(s)\cdot u_i(s)$ expected utility
$x^* \in \Delta$
mixed Nash equilibrium (MNE) of $G$ if
$x^*$ is PNE of mixed extension
$\iff U_i(x^*) \geq U_i(x_i,x^*_{-i})$ f.a. $x_i \in \Delta(S_i), i \in N$.
Lem. 1:24: In zero-sum game we have for any $x^* \in \Delta(S_1)$, $y^* \in \Delta(S_2)$:
\[\min_{y \in \Delta(S_2)}U_1(x^*,y) = \min_{j \in [n]}U_1(x^*,j) \quad\text{and}\quad \max_{x \in \Delta(S_1)}U_1(x,y^*) = \max_{i \in [m]}U_1(i,y^*).\]
Thm. 1.25 (Minimax-Thm of Neumann): Every finite zero sum game has a MNE.
Thm. A.3: Given any $(x^*, z^*)$ and $(y^*,w^*)$ for
\begin{align}\label{eq:LP}\tag{LP}
\begin{array}{rrcrcl}
\max_{x,z} & c^Tx &+& d^Tz && \\
\text{s.t. } & Ax &+& Bz &\leq & a \\
& Cx &+& Dz &= & b \\
& x & & &\geq &0
\end{array}
\end{align}
\begin{align}\label{eq:DP}\tag{DP}
\begin{array}{rrcrcl}
\min_{y,w} & a^Ty &+& b^Tw && \\
\text{s.t. } & A^Ty &+& C^Tw &\geq & c \\
& B^Ty &+& D^Tw &= & d \\
& y & & &\geq &0
\end{array}
\end{align}
If both are feasible solutions, then $c\transp x^* + d\transp z^* \leq a\transp y^* + b\transp w^*$
If both are optimal solutions, then $c\transp x^* + d\transp z^* = a\transp y^* + b\transp w^*$
x_1
x_2
1 2
1 2
x_1
x_2
1 2
1 2
Obs. 1.8: $x^* \in \Delta$ is MNE $\iff x^* \in B(x^*) \coloneqq \prod_i B_i(x^*_{-i})$
Thm. 1.27 (Brouwer's Fixed Point Thm): Given $f: K \to K$ with
$K \subseteq \IR^k$ non-empty, compact, convex
$f$ continuous
Then, $f$ has a fixed point, i.e., $\exists x^* \in K: f(x^*) = x^*$.
Thm. 1.28: Every finite game has a MNE.
Matching Pennies:
$H$ $T$ $H$ $(1,-1)$ $(-1,1)$ $T$ $(-1,1)$ $(1,-1)$
x_{1T}
x_{1H}
1
1
\Delta(S_1)
x_{2T}
x_{2H}
1
1
\Delta(S_2)
H
\Delta(S_1)
T
H
\Delta(S_2)
T